<?php
/**
 * 插入派讯算法
 * @param arr
 * author yajun
 * time 2013-7-5
 */
function insertsort($arr)
{
	$len = count($arr);
	if($len <= 1)
	{
		return $arr;
	}
	$sort[] = $arr[0];
	for($i = 1; $i < $len ; $i++)
	{
		if($arr[$i] >= $arr[$i-1])
		{
			$sort[] = $arr[$i];
		}
		else 
		{
			break;
		}
	}
	for($j = $i ; $j < $len; $j++)
	{
		if($arr[$j] >= $arr[$j-1])
		{
			$sort[] = $arr[$j];
			continue;
		}
		for($m = $j-2 ; $m >= 0; $m-- )
		{
			if($arr[$j] > $sort[$m])
			{
				for( $n = $j ; $n >= $m ; $n--)
				{
					$sort[$n] = $sort[$n-1];
				}
				$sort[$m+1] = $arr[$j];
				break;
			}
		}
	}
	return $sort;
}
date_default_timezone_set('Asia/Shanghai');
var_dump(insertsort(array(1,3,5,2,4)));